package P1线性结构.LeetCode单调栈;

import java.util.LinkedList;

public class LeetCode503 {
    public int[] nextGreaterElements(int[] nums) {
        int[] ret = new int[nums.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = -1;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums.length * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[i % nums.length] > nums[stack.peek()]) {
                ret[stack.pop()] = nums[i % nums.length];
            }
            //栈为空 或 当前比栈顶小于等于 进栈
            stack.push(i % nums.length);
        }
        return ret;
    }
}
